// let maximumTime = function (time) {
//     const arr = Array.from(time);
//     if (arr[0] === '?') {
//         arr[0] = ('4' <= arr[1] && arr[1] <= '9') ? '1' : '2';
//     }
//     if (arr[1] === '?') {
//         arr[1] = (arr[0] === '2') ? '3' : '9';
//     }
//     if (arr[3] === '?') {
//         arr[3] = '5';
//     }
//     if (arr[4] === '?') {
//         arr[4] = '9';
//     }
//     return arr.join('');
// };
//
// let time = "2?:?0";
// console.log(maximumTime(time));


// 1、HJ1 字符串最后一个单词的长度
// hello nowcoder

// var readline = require('readline');
// const rl = readline.createInterface({
//     input: process.stdin,
//     output: process.stdout
// });
// rl.on('line', function(line){
//     // var tokens = line.split(' ');
//     var arr = line.split(' ')
//     var str = arr.pop()
//     console.log(str.length)
// });
// HJ1 字符串最后一个单词的长度
// const readline = require("readline");
// const rl = readline.createInterface({
//     input: process.stdin,
//     output:process.stdout
// });
//
// function getResolve(s) {
//     if (/([^\s]+)$/.test(s.trim())) {
//         return RegExp.$1.length;
//     }
//
//     return 0;
// }
//
// rl.on('line', function(line){
//     console.log(getResolve(line));
// });
//
// rl.on('close', function() {
//     process.exit(0);
// });


// 2、HJ2 计算某字母出现次数:
// ABCabc
// A
// let readline = require('readline');
// const rl = readline.createInterface({
//     input: process.stdin,
//     output: process.stdout
// });
// let lines = [];
// let lineIndex = 0;
// let filters = [];
// rl.on('line', (line)=> {
//     if (lineIndex === 0) {
//         lines.push(line);
//         lineIndex += 1;
//     } else {
//         lines.push(line);
//         filters = [...lines[0]].filter((item)=> {
//             return item.toLowerCase() === lines[1].toLowerCase()
//         })
//         lineIndex = 0;
//         console.log(filters.length);
//     }
// })

// HJ3 明明的随机数
// 第一行输入个数，余下行输入要去重的数字序列：ctrl+c结束连续输入
// 3
// 2
// 2
// 1

// let readline = require('readline');
// let r1 = readline.createInterface({
//     input: process.stdin,
//     output: process.stdout
// });
// let line = -1;
// let len = 0;
// let arr = [];
// let obj = {};
//
// r1.on('line', function (input){
//     input = parseInt(input);
//     if (line == -1) {
//         line = 1;
//         len = input;
//         arr = [];
//         obj = {};
//     } else {
//         if (!obj[input]) {
//             obj[input] = 1;
//             arr.push(input);
//         }
//         if (len === 1) {
//             console.log(arr.sort(function(a,b) {return a-b;}).join("\n"));
//             line = -1;
//         }
//         len--;
//     }
// });

// let Site = (function () {
//     function Site() {}
//     Site.prototype.name = function () {
//         console.log("runoob");
//     };
//     return Site;
// }());
// let obj = new Site();
// obj.name();

// function addNumbers() {
//     let nums = [];
//     for (let _i=0; _i<arguments.length; _i++) {
//         nums[_i] = arguments[_i];
//     }
//     let i;
//     let sum = 0;
//     for (i=0; i<nums.length; i++) {
//         sum = sum+nums[i];
//     }
//     console.log(sum);
// }
// addNumbers(1,2,3);

// let someArray = [1, "string", false];
//
// for (let entry of someArray) {
//     console.log(entry); // 1, "string", false
// }

// var readline = require('readline');
// const rl = readline.createInterface({
//     input: process.stdin,
//     ouput: process.stdout
// });
// rl.on('line', function(line) {
//     var output = parseInt(line, 16);
//     console.log(output)
// })

// 输入：
// 3
// 1 2 5
// 4
// -1 0 3 2
// 复制
// 输出：
// -101235


// const lines = [
//     '3',
//     '1 2 5',
//     '4',
//     '-1 0 3 2'
// ]
// let index = 0;
// function readline() {
//     return lines[index++];
// }
//
// while(line = readline())
// {
//     if((line = readline()) === undefined) break;
//     var arr_1 = line.split(' ').map(function(str){ return parseInt(str) })
//     line = readline()
//     if((line = readline()) === undefined) break;
//     var arr_2 = line.split(' ').map(function(str){ return parseInt(str) })
//     var len_2 = arr_2.length
//     for(var val of arr_1){
//         if(arr_2[ len_2-1 ] < val){ arr_2.push(val);   len_2++;   continue; }
//         for(var i=0; i<len_2; i++)
//             if(arr_2[i] >= val){
//                 if(arr_2[i] == val) break
//                 arr_2.splice(i, 0, val)
//                 len_2++;   break;
//             }
//     }
//     var res = ''
//     arr_2.forEach(function(val){
//         res += val.toString()
//     })
//     console.log(res)
// }


// // JavaScript Node
// var readline=require('readline').createInterface({
//     input:process.stdin,
//     output:process.stdout
// });
//
// var a=[];
// readline.on('line',function(line){
//     a.push(line.trim());
//     if(a.length==4){
//         var str2Arr = a[1].split(' ');
//         var str3Arr =a[3].split(' ');
//         var str6Arr = str2Arr.concat(str3Arr);
//         var str4Arr=[];
//         for(var i=0;i<str6Arr.length;i++){
//             if(str4Arr.indexOf(str6Arr[i])== -1){
//                 str4Arr.push(str6Arr[i]);
//             }
//         }
//         var str5Arr = str4Arr.sort(function(a,b){
//             return a-b;
//         })
//         console.log(str5Arr.join(''));  a.length=0;
//
//     }
// })


// var circularArrayLoop = function(nums) {
//     const n = nums.length;
//     for (let i = 0; i < n; i++) {
//         if (nums[i] === 0) {
//             continue;
//         }
//         let slow = i, fast = next(nums, i);
//         // 判断非零且方向相同
//         while (nums[slow] * nums[fast] > 0 && nums[slow] * nums[next(nums, fast)] > 0) {
//             if (slow === fast) {
//                 if (slow !== next(nums, slow)) {
//                     return true;
//                 } else {
//                     break;
//                 }
//             }
//             slow = next(nums, slow);
//             fast = next(nums, next(nums, fast));
//         }
//         let add = i;
//         while (nums[add] * nums[next(nums, add)] > 0) {
//             const tmp = add;
//             add = next(nums, add);
//             nums[tmp] = 0;
//         }
//     }
//     return false;
// }
//
// const next = (nums, cur) => {
//     const n = nums.length;
//     return ((cur + nums[cur]) % n + n) % n; // 保证返回值在 [0,n) 中
// }
//
// let readLine = require("readline");
// const rl = readLine.createInterface({
//     input: process.stdin,
//     output: process.stdout
// });
//
// rl.on("line", function(line) {
//     let strInput = JSON.parse(line);
//     console.log(circularArrayLoop(strInput));
// })


// var kWeakestRows = function (mat, k) {
//     return mat.map((a, i) => [a, `${i}`.padStart(2, '0')]).sort().map(a => +a[1]).slice(0, k);
// };
//
// var kWeakestRowsTwo = function (mat, k) {
//     const map = new Map();
//     mat.forEach((a, i) => map.set(a, i));
//     mat.sort();
//     return Array.from({ length: k }, (_, i) => map.get(mat[i]));
// };
//
// var kWeakestRowsThree = function (mat, k) {
//     const ans = [0], n = mat.length;
//     for (let i = 1; i < n; i++) {
//         // 比最后一项大就跳过
//         if (ans[k - 1] < mat[i]) continue;
//         let l = 0, r = ans.length;
//         while (l < r) {
//             const mid = l + ((r - l) >> 1);
//             if (mat[i] > mat[ans[mid]]) l = mid + 1;
//             else if (mat[i] < mat[ans[mid]]) r = mid;
//             // 数组相等根据下标大小选择插入位置
//             else if (i > ans[mid]) l = mid + 1;
//             else r = mid;
//         }
//         // 插入元素
//         ans.splice(l, 0, i);
//         // 删除多余元素
//         ans.length = k;
//     }
//     return ans;
// };
//
//
// let readLine = require("readline");
// const rl = readLine.createInterface({
//     input: process.stdin,
//     output: process.stdout
// });
//
// let rows
// rl.on("line", function (line) {
//     rows = line.split("\n");
//     console.log(rows[0], rows[1])
//     // let mat = JSON.parse(line[0]);
//     // let k = parseInt(line[1]);
//     // console.log(mat, k);
// })


// let unhappyFriends = function(n, preferences, pairs) {
//     const order = new Array(n).fill(0).map(() => new Array(n).fill(0));
//     for (let i = 0; i < n; i++) {
//         for (let j = 0; j < n - 1; j++) {
//             order[i][preferences[i][j]] = j;
//         }
//     }
//     const match = new Array(n).fill(0);
//     for (const pair of pairs) {
//         let person0 = pair[0], person1 = pair[1];
//         match[person0] = person1;
//         match[person1] = person0;
//     }
//     let unhappyCount = 0;
//     for (let x = 0; x < n; x++) {
//         const y = match[x];
//         const index = order[x][y];
//         for (let i = 0; i < index; i++) {
//             const u = preferences[x][i];
//             const v = match[u];
//             if (order[u][x] < order[u][v]) {
//                 unhappyCount++;
//                 break;
//             }
//         }
//     }
//     return unhappyCount;
// };
//
//
// // 多行输入（固定行数输入）
// let readLine = require("readline");
// const rl = readLine.createInterface({
//     input: process.stdin,
//     output: process.stdout
// });
//
// let k = 3;
// let rows = [];
// rl.on("line", function (line) {
//     rows.push(line);
//     if (k === rows.length) {
//         // console.log(rows[0], rows[1], rows[2]);
//         let n = parseInt(rows[0]);
//         let preferences = JSON.parse(rows[1]);
//         let pairs = JSON.parse(rows[2]);
//
//         console.log(unhappyFriends(n, preferences, pairs));
//
//         // 重置
//         rows.length = 0;
//     }
// })


// // 多行输入（第一行输入的数据是接下来输入数据的行数）
// const readLine = require("readline");
// const rl = readLine.createInterface({
//     input: process.stdin,
//     output: process.stdout
// });
//
// let k = -1;
// let rows = [];
// rl.on("line", function (line) {
//     if (k < 0) {
//         k = parseInt(line.trim());
//     } else {
//         rows.push(line.trim());
//         if (k === rows.length) {
//             // 输入行数等于设定的行数k时，开始逻辑处理
//             console.log(rows[0], rows[1], rows[2]);
//             // 这儿放写的功能函数
//         }
//
//         // 重置
//         rows.length = 0;
//         k = -1;
//     }
//
// })
//
//
// let somethingFunction = function(arrayInput) {
//     return "函数返回值"
// }
//
// // 单行输入
// let readLine = require("readline");
// const rl = readLine.createInterface({
//     input: process.stdin,
//     output: process.stdout
// });
//
//
// rl.on("line", function (line) {
//     let arrayInput = JSON.parse(line);
//     console.log(somethingFunction(arrayInput));
// })


// let escapeGhosts = function(ghosts, target) {
//     const source = [0, 0];
//     const distance = manhattanDistance(source, target);
//     for (const ghost of ghosts) {
//         const ghostDistance = manhattanDistance(ghost, target);
//         if (ghostDistance <= distance) {
//             return false;
//         }
//     }
//     return true;
// }
//
// const manhattanDistance = (point1, point2) => {
//     return Math.abs(point1[0] - point2[0]) + Math.abs(point1[1] - point2[1]);
// }
//
// let n = 2;
// let rows = []
// let readLine = require("readline");
// const rl = readLine.createInterface({
//     input: process.stdin,
//     output: process.stdout
// });
// rl.on("line", function (line) {
//     rows.push(line);
//     if (n === rows.length) {
//         let ghostsInput = JSON.parse(rows[0]);
//
//         let targetInput = JSON.parse(rows[1]);
//         console.log(escapeGhosts(ghostsInput,  targetInput));
//
//         rows.length = 0;
//     }
// })



// let allPathsSourceTarget = function(graph) {
//     const stack = [], ans = [];
//
//     const dfs = (graph, x, n) => {
//         if (x === n) {
//             ans.push(stack.slice());
//             return;
//         }
//         for (const y of graph[x]) {
//             stack.push(y);
//             dfs(graph, y, n);
//             stack.pop();
//         }
//     }
//
//     stack.push(0);
//     dfs(graph, 0, graph.length - 1);
//     return ans;
// };
//
// let readLine = require("readline");
// const rl = readLine.createInterface({
//     input: process.stdin,
//     output: process.stdout
// });
// rl.on("line", function (line) {
//     let graph = JSON.parse(line);
//     console.log(allPathsSourceTarget(graph));
// });



// let corpFlightBookings = function(bookings, n) {
//     const nums = new Array(n).fill(0);
//     for (const booking of bookings) {
//         nums[booking[0] - 1] += booking[2];
//         if (booking[1] < n) {
//             nums[booking[1]] -= booking[2];
//         }
//     }
//     for (let i = 1; i < n; i++) {
//         nums[i] += nums[i - 1];
//     }
//     return nums;
// };
//
// let lineNum = 2;
// let rows = []
// let readLine = require("readline");
// const rl = readLine.createInterface({
//     input: process.stdin,
//     output: process.stdout
// });
// rl.on("line", function (line) {
//     rows.push(line);
//     if (rows.length === lineNum) {
//         let bookings = JSON.parse(rows[0]);
//         let n = parseInt(rows[1]);
//         let result = corpFlightBookings(bookings, n);
//         console.log(result);
//
//         rows.length = 0;
//     }
// })




// let numberOfBoomerangs = function(points) {
//     let ans = 0;
//     for (const p of points) {
//         const cnt = new Map();
//         for (const q of points) {
//             const dis = (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);
//             cnt.set(dis, (cnt.get(dis) || 0) + 1);
//         }
//         for (const [_, m] of cnt.entries()) {
//             ans += m * (m - 1);
//         }
//     }
//     return ans;
// };
//
//
// let readLine = require("readline");
// const rl = readLine.createInterface({
//     input: process.stdin,
//     output: process.stdout
// });
// rl.on("line", function (line) {
//     let points = JSON.parse(line);
//     console.log(numberOfBoomerangs(points));
// })



// let isValidSudoku = function(board) {
//     const rows = new Array(9).fill(0).map(() => new Array(9).fill(0));
//     const columns = new Array(9).fill(0).map(() => new Array(9).fill(0));
//     const subboxes = new Array(3).fill(0).map(() => new Array(3).fill(0).map(() => new Array(9).fill(0)));
//     for (let i = 0; i < 9; i++) {
//         for (let j = 0; j < 9; j++) {
//             const c = board[i][j];
//             if (c !== '.') {
//                 const index = c.charCodeAt() - '0'.charCodeAt() - 1;
//                 rows[i][index]++;
//                 columns[j][index]++;
//                 subboxes[Math.floor(i / 3)][Math.floor(j / 3)][index]++;
//                 if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[Math.floor(i / 3)][Math.floor(j / 3)][index] > 1) {
//                     return false;
//                 }
//             }
//         }
//     }
//     return true;
// };
//
// let readLine = require("readline");
// const rl = readLine.createInterface({
//     input: process.stdin,
//     output: process.stdout
// });
// rl.on("line", function (line) {
//     let board = JSON.parse(line);
//     console.log(isValidSudoku(board));
//
//     console.log(board)
// })


// let RandomizedSet = function () {
//     // numToLocation存储了每个数值及其在数组nums中的下标
//     this.numToLocation = new Map();
//     // 数值保存在动态数组nums中
//     this.nums = [];
// };
//
// /**
//  * @param {number} val
//  * @return {boolean}
//  */
// RandomizedSet.prototype.insert = function (val) {
//     /* // 如果 val 不存在集合中，则插入并返回 true，否则直接返回 false */
//
//     if (this.numToLocation.has(val)) {
//         return false;
//     }
//     // 如果之前没有该数值，则把它添加到数组nums的尾部，并把它和它在数组中的下标添加到哈希表中
//     this.numToLocation.set(val, this.nums.length);
//     this.nums.push(val);
//     return true;
// };
//
// /**
//  * @param {number} val
//  * @return {boolean}
//  */
// RandomizedSet.prototype.remove = function (val) {
//     /* // 如果 val 在集合中，则删除并返回 true，否则直接返回 false */
//     // 数据集中是否已经包含该数值，如果没有包含则不能删除
//     if (!this.numToLocation.has(val)) {
//         return false;
//     }
//     // 从哈希表中删除一个元素是O(1),
//     let location = this.numToLocation.get(val);
//     this.numToLocation.set(this.nums[this.nums.length - 1], location);
//     this.numToLocation.delete(val);
//     // 数组删除对应，这里是把数据最末位的元素覆盖要删除的元素，再把数组长度减1，通过这种技巧来达到时间复杂度为O(1)
//     this.nums[location] = this.nums[this.nums.length - 1];
//     this.nums.length--;
//     return true;
// };
//
// /**
//  * @return {number}
//  */
// RandomizedSet.prototype.getRandom = function () {
//     /* // 从集合中等概率地随机获得一个元素 */
//     // 随机生成0到this.nums.length范围内的一个整数
//     let p = parseInt(Math.random() * this.nums.length);
//     return this.nums[p];
// };
//
// /**
//  * Your RandomizedSet object will be instantiated and called as such:
//  * var obj = new RandomizedSet()
//  * var param_1 = obj.insert(val)
//  * var param_2 = obj.remove(val)
//  * var param_3 = obj.getRandom()
//  */
//
//
// let readLine = require("readline");
// const rl = readLine.createInterface({
//    input: process.stdin,
//    output: process.stdout
// });
//
// let rows = []
// let lineNum = 2
//
// rl.on("line", function (line) {
//     rows.push(line);
//     if (rows.length === lineNum) {
//         console.log("rows: ", rows);
//
//         let result = []
//         let obj = new RandomizedSet();
//         result.push(null);
//
//         let commands = JSON.parse(rows[0]);
//         let nums = JSON.parse(rows[1]);
//
//         for (let i=0; i<commands.length; i++) {
//             let c = commands[i];
//             if (c === "insert") {
//                 result.push(obj.insert(nums[i][0]));
//             } else if (c === "remove") {
//                 result.push(obj.remove(nums[i][0]));
//             } else if (c === "getRandom") {
//                 result.push(obj.getRandom());
//             }
//         }
//
//         console.log(result);
//
//         // 重置
//         rows.length = 0;
//     }
//
// })
//
// /*
// ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
// [[], [1], [2], [2], [], [1], [2], []]
// * */


// // 宽度优先搜索+递归
// let maxDepth = function(root) {
//     if (!root) {
//         return 0;
//     }
//     let maxChildDepth = 0;
//     const children = root.children;
//     for (const child of children) {
//         const childDepth = maxDepth(child);
//         maxChildDepth = Math.max(maxChildDepth, childDepth);
//     }
//     return maxChildDepth + 1;
// };
//
// // 广度优先搜索
// let maxDepthTwo = function(root) {
//     if (!root) {
//         return 0;
//     }
//     const queue = [];
//     queue.push(root);
//     let ans = 0;
//     while (queue.length) {
//         let size = queue.length;
//         while (size > 0) {
//             const node = queue.shift();
//             const children = node.children;
//             for (const child of children) {
//                 queue.push(child);
//             }
//             size--;
//         }
//         ans++;
//     }
//     return ans;
// };


// let maxIncreaseKeepingSkyline = function(grid) {
//     const n = grid.length;
//     const rowMax = new Array(n).fill(0);
//     const colMax = new Array(n).fill(0);
//     for (let i = 0; i < n; i++) {
//         for (let j = 0; j < n; j++) {
//             rowMax[i] = Math.max(rowMax[i], grid[i][j]);
//             colMax[j] = Math.max(colMax[j], grid[i][j]);
//         }
//     }
//     let ans = 0;
//     for (let i = 0; i < n; i++) {
//         for (let j = 0; j < n; j++) {
//             ans += Math.min(rowMax[i], colMax[j]) - grid[i][j];
//         }
//     }
//     return ans;
// };
//
// let readLines = require("readline");
// const rl = readLines.createInterface({
//    input: process.stdin,
//    output: process.stdout
// });
//
// rl.on("line", function (line) {
//     let grid = JSON.parse(line);
//     console.log(maxIncreaseKeepingSkyline(grid));
// })


// // 方法二：枚举起点
// let countBattleshipsTwo = function(board) {
//     const row = board.length;
//     const col = board[0].length;
//     let ans = 0;
//     for (let i = 0; i < row; ++i) {
//         for (let j = 0; j < col; ++j) {
//             if (board[i][j] === 'X') {
//                 if (i > 0 && board[i - 1][j] === 'X') {
//                     continue;
//                 }
//                 if (j > 0 && board[i][j - 1] === 'X') {
//                     continue;
//                 }
//                 ans++;
//             }
//         }
//     }
//     return ans;
// };
//
//
// // 方法一：遍历扫描
// let countBattleships = function(board) {
//     const row = board.length;
//     const col = board[0].length;
//     let ans = 0;
//     for (let i = 0; i < row; ++i) {
//         for (let j = 0; j < col; ++j) {
//             if (board[i][j] === 'X') {
//                 board[i][j] = '.';
//                 for (let k = j + 1; k < col && board[i][k] === 'X'; ++k) {
//                     board[i][k] = '.';
//                 }
//                 for (let k = i + 1; k < row && board[k][j] === 'X'; ++k) {
//                     board[k][j] = '.';
//                 }
//                 ans++;
//             }
//         }
//     }
//     return ans;
// };
//
// let readLines = require("readline");
// const rl = readLines.createInterface({
//    input: process.stdin,
//    output: process.stdout
// });
//
// rl.on("line", function (line) {
//     let grid = JSON.parse(line);
//     console.log(countBattleships(grid));
// })



// let visiblePoints = function(points, angle, location) {
//     let sameCnt = 0;
//     const polarDegrees = [];
//     let locationX = location[0];
//     let locationY = location[1];
//     for (let i = 0; i < points.length; ++i) {
//         const x = points[i][0];
//         const y = points[i][1];
//         if (x === locationX && y === locationY) {
//             sameCnt++;
//             continue;
//         }
//         const degree = Math.atan2(y - locationY, x - locationX);
//         polarDegrees.push(degree);
//     }
//     polarDegrees.sort((a, b) => a - b);
//
//     const m = polarDegrees.length;
//     for (let i = 0; i < m; ++i) {
//         polarDegrees.push(polarDegrees[i] + Math.PI * 2);
//     }
//
//     let maxCnt = 0;
//     const toDegree = angle * Math.PI / 180;
//     for (let i = 0; i < m; ++i) {
//         const iteration = binarySearch(polarDegrees, polarDegrees[i] + toDegree, false);
//         maxCnt = Math.max(maxCnt, iteration - i);
//     }
//     return maxCnt + sameCnt;
// };
//
// const binarySearch = (nums, target, lower) => {
//     let left = 0, right = nums.length - 1;
//     let ans = nums.length;
//     while (left <= right) {
//         const mid = Math.floor((left + right) / 2);
//         if (nums[mid] > target || (lower && nums[mid] >= target)) {
//             right = mid - 1;
//             ans = mid;
//         } else {
//             left = mid + 1;
//         }
//     }
//     return ans;
// }



// let numFriendRequests = function(ages) {
//     const cnt = new Array(121).fill(0);
//     for (const age of ages) {
//         ++cnt[age];
//     }
//     const pre = new Array(121).fill(0);
//     for (let i = 1; i <= 120; ++i) {
//         pre[i] = pre[i - 1] + cnt[i];
//     }
//     let ans = 0;
//     for (let i = 15; i <= 120; ++i) {
//         if (cnt[i] > 0) {
//             const bound = Math.floor(i * 0.5 + 8);
//             ans += cnt[i] * (pre[i] - pre[bound - 1] - 1);
//         }
//     }
//     return ans;
// };
//
//
// let readLine = require("readline");
// const rl = readLine.createInterface({
//     input: process.stdin,
//     output: process.stdout
// });
// rl.on("line", function (line) {
//     let ages = JSON.parse(line);
//     console.log(numFriendRequests(ages));
// })



// let construct2DArray = function(original, m, n) {
//     if (original.length !== m * n) {
//         return [];
//     }
//     const ans = new Array(m).fill(0).map(() => new Array(n).fill(0));
//     for (let i = 0; i < original.length; i += n) {
//         ans[Math.floor(i / n)].splice(0, n, ...original.slice(i, i + n))
//     }
//     return ans;
// };
//
//
// let readLine = require("readline");
// const rl = readLine.createInterface({
//     input: process.stdin,
//     output: process.stdout
// });
// let rows = []
// rl.on("line", function (line) {
//     rows.push(line);
//     if (rows.length === 3) {
//         let original = JSON.parse(rows[0]);
//         let m = parseInt(rows[1]);
//         let n = parseInt(rows[2]);
//         console.log(construct2DArray(original, m, n));
//         // 重置
//         rows.length = 0;
//     }
// })



// let reverseOnlyLetters = function(s) {
//     const n = s.length;
//     const arr = [...s];
//     let left = 0, right = n - 1;
//     while (true) {
//         while (left < right && !(/^[a-zA-Z]+$/.test(s[left]))) { // 判断左边是否扫描到字母
//             left++;
//         }
//         while (right > left && !(/^[a-zA-Z]+$/.test(s[right]))) { // 判断右边是否扫描到字母
//             right--;
//         }
//         if (left >= right) {
//             break;
//         }
//         swap(arr, left, right);
//         left++;
//         right--;
//     }
//     return arr.join('');
// };
//
// const swap = (arr, left, right) => {
//     const temp = arr[left];
//     arr[left] = arr[right];
//     arr[right] = temp;
// }
//
// let readLine = require("readline");
// const rl = readLine.createInterface({
//     input: process.stdin,
//     output: process.stdout
// });
// rl.on("line", function (line) {
//     console.log(reverseOnlyLetters(line));
// })


// var reorderLogFiles = function(logs) {
//     const length = logs.length;
//     const arr = new Array(length).fill(0);
//     for (let i = 0; i < length; i++) {
//         arr[i] = [logs[i], i];
//     }
//     arr.sort((a, b) => logCompare(a, b));
//     const reordered = new Array(length).fill(0);
//     for (let i = 0; i < length; i++) {
//         reordered[i] = arr[i][0];
//     }
//     return reordered;
// }
//
// const logCompare = (log1, log2) => {
//     const split1 = split(log1[0], " ");
//     const split2 = split(log2[0], " ");
//     const isDigit1 = isDigit(split1[1][0]);
//     const isDigit2 = isDigit(split2[1][0]);
//     if (isDigit1 && isDigit2) {
//         return log1[1] - log2[1];
//     }
//     if (!isDigit1 && !isDigit2) {
//         const sc = compareTo(split1[1], split2[1]);
//         if (sc !== 0) {
//             return sc;
//         }
//         return compareTo(split1[0], split2[0]);
//     }
//     return isDigit1 ? 1 : -1;
// };
//
// const isDigit = (ch) => {
//     return parseFloat(ch).toString() === "NaN" ? false : true;
// }
//
// const compareTo = (left, right) => {
//     for (let i = 0; i < Math.min(left.length, right.length); i++) {
//         if (left[i].charCodeAt() < right[i].charCodeAt()) {
//             return -1;
//         }
//         if (left[i].charCodeAt() > right[i].charCodeAt()) {
//             return 1;
//         }
//     }
//     if (left.length === right.length) {
//         return 0;
//     }
//     if (left.length > right.length) {
//         return 1;
//     }
//     return -1;
// }
//
// const split = (str, separator) => {
//     const firstItem = str.split(separator)[0];
//     const ret = [firstItem];
//     const index = str.indexOf(" ");
//     ret.push(str.slice(index + 1, str.length));
//     return ret;
// }


// let findTheWinner = function(n, k) {
//     const queue = [];
//     for (let i=1; i<=n; i++) {
//         queue.push(i);
//     }
//     while (queue.length > 1) {
//         for (let i=1; i<k; i++) {
//             queue.push(queue.shift());
//         }
//         queue.shift();
//     }
//     return queue[0];
// }
//
// let readLine = require("readline");
// const rl = readLine.createInterface({
//     input: process.stdin,
//     output: process.stdout
// });
// let rows = [];
// rl.on("line", function (line) {
//     rows.push(line);
//     if (rows.length === 2) {
//         let n = parseInt(rows[0]);
//         let k = parseInt(rows[1]);
//         console.log(findTheWinner(n, k));
//         rows.length = 0;
//     }
// })


// var defangIPaddr = function(address) {
//     // 单双引号均可
//     return address.replaceAll('\.', '[.]');
// };

// var defangIPaddr = function(address) {
//     // node.js 版本 v14.15.1, 没有实现String.prototype.replaceAll，所以报错
//     return address.replaceAll('\.', '[.]');
//     // 那就更新，下载覆盖 node.js 16.15.1 -> 这个版本支持!!
// };
//
// let readLine = require("readline");
// const rl = readLine.createInterface({
//    input: process.stdin,
//    output: process.stdout
// });
// rl.on("line", function(line) {
//     console.log("line: ", line);
//     let address = JSON.parse(line);
//     console.log("address: ", address);
//     // let res = defangIPaddr(address);
//     // console.log("res: ", res);
//     // console.log("res: ", defangIPaddr(address));
//     console.log(defangIPaddr(address));
// })


// /**
//  * @param {number[]} position
//  * @return {number}
//  */
// var minCostToMoveChips = function(position) {
//     let odd = 0, event = 0;
//     for (let i=0; i<position.length; ++i) {
//         let p = position[i];
//         p % 2 === 0 ? event++ : odd++;
//     }
//     return Math.min(odd, event);
// };
//
//
// let readLine = require("readline");
// const rl = readLine.createInterface({
//     input: process.stdin,
//     output: process.stdout
// });
// rl.on(
//     "line", function (line) {
//         // let p = [1,2,3];
//         let p = JSON.parse(line);
//         let res = minCostToMoveChips(p);
//         console.log(res);
//     }
// )


// /**
//  * Definition for a binary tree node.*/
// function TreeNode(val, left, right) {
//     this.val = (val===undefined ? 0 : val)
//     this.left = (left===undefined ? null : left)
//     this.right = (right===undefined ? null : right)
// }
//
//
// // 方法一：深度优先搜索
// /**
//  * @param {TreeNode} root
//  * @param {number} val
//  * @param {number} depth
//  * @return {TreeNode}
//  */
// var addOneRow = function(root, val, depth) {
//     if (!root) {
//         return null;
//     }
//     if (depth === 1) {
//         return new TreeNode(val, root, null);
//     }
//     if (depth === 2) {
//         root.left = new TreeNode(val, root.left, null);
//         root.right = new TreeNode(val, null, root.right);
//     } else {
//         root.left = addOneRow(root.left, val, depth - 1);
//         root.right = addOneRow(root.right, val, depth - 1);
//     }
//     return root;
// };
//
// // 方法二：广度优先搜索
// var addOneRow2 = function(root, val, depth) {
//     if (depth === 1) {
//         return new TreeNode(val, root, null);
//     }
//     let curLevel = [];
//     curLevel.push(root);
//     for (let i = 1; i < depth - 1; i++) {
//         const tmp = [];
//         for (const node of curLevel) {
//             if (node.left) {
//                 tmp.push(node.left);
//             }
//             if (node.right) {
//                 tmp.push(node.right);
//             }
//         }
//         curLevel = tmp;
//     }
//     for (const node of curLevel) {
//         node.left = new TreeNode(val, node.left, null);
//         node.right = new TreeNode(val, null, node.right);
//     }
//     return root;
// };
//
//
// /**
//  * @param {number[]} nums
//  * @param {number} n
//  * @return {number[]}
//  */
// var shuffle = function(nums, n) {
//     const ans = new Array(2 * n).fill(0);
//     for (let i=0; i<n; i++) {
//         ans[2 * i] = nums[i];
//         ans[2 * i + 1] = nums[i + n];
//     }
//     return ans;
// };


/**
 * Definition for a binary tree node. */
function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

/**
 * @param {TreeNode} root
 * @return {number}
 */
var longestUnivaluePath = function(root) {
    let res = 0;
    const dfs = (root) => {
        if (!root) {
            return 0;
        }
        let left = dfs(root.left), right = dfs(root.right);
        let left1 = 0, right1 = 0;
        if (root.left && root.left.val === root.val) {
            left1 = left + 1;
        }
        if (root.right && root.right.val === root.val) {
            right1 = right + 1;
        }
        res = Math.max(res, left1 + right1);
        return Math.max(left1, right1);
    }
    dfs(root);
    return res;
};


// node.js -> js 版本太高，导致npm安装会报错：The package-lock.json file was created with an old version of npm